package offer;

import java.nio.charset.StandardCharsets;
import java.util.*;

/**
 * @Author Elephas
 * @Date 2022/1/29
 **/
@FunctionalInterface
public interface GroupAnagrams {
    List<List<String>> groupAnagrams(String[] strs);
}
class GroupAnagramsImpl1 implements GroupAnagrams{
    final static String[] TEST_01 = new String[]{"eat", "tea", "tan", "ate", "nat", "bat"};
    final static String[] TEST_02 = new String[]{"hhhhu","tttti","tttit","hhhuh","hhuhh","tittt"};
    public static void main(String[] args) {
        new GroupAnagramsImpl2().groupAnagrams(TEST_01);
    }
    @Override
    @Deprecated
    /*
        没写出来，复杂度没有组织好，重写
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<>();
        Map<Set<Character>,List<String>> map = new HashMap<>();
        List<String> emptyList = new ArrayList<>();

        for (int i = 0; i < strs.length; i++) {
            if("".equals(strs[i]) || strs[i] == null){
                emptyList.add(strs[i]);
                continue;
            }
            boolean appeared = false;
            for(Map.Entry entry : map.entrySet()){
                boolean contains = true;
                Set<Character> tempSet = (Set<Character>) entry.getKey();
                List<String> tempList = (List<String>) entry.getValue();
                for (int j = 0; j < strs[i].length(); j++) {
                    if(!tempSet.contains(strs[i].charAt(j))){
                        contains = false;
                        break;
                    }
                }

                if(contains && tempList.get(0).length() == strs[i].length()){
                    tempList.add(strs[i]);
                    appeared = true;
                }
            }
            if(!appeared){
                Set<Character> tempSet = new HashSet<>();
                for (int j = 0; j < strs[i].length(); j++) {
                    tempSet.add(strs[i].charAt(j));
                }
                List<String> tempList = new ArrayList<>();
                tempList.add(strs[i]);
                map.put(tempSet,tempList);
            }
        }

        for(Map.Entry entry:map.entrySet()){
            ans.add((List<String>) entry.getValue());
        }
        if(!emptyList.isEmpty()) {
            ans.add(emptyList);
        }
        return ans;
    }
}
class GroupAnagramsImpl2 implements GroupAnagrams{

    /**
     * 过不了大样本测试，需要优化时间复杂度
     * 1.isAnagram 判断两个字符串是否为字母异位词，对 str1 简历哈希表遍历一次 str1，对 str2 遍历一次，时间复杂度为o(m+n)
     * 2.groupAnagrams 外侧循环，对于每一组 key 都进行一次比较，key 最多为 strs[i].length 个
     * 最终时间复杂度为 o(k(m+n))
     */
    @Override
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        List<String> emptyList = new LinkedList<>();
        for (int i = 0; i < strs.length; i++) {
            String current = strs[i];
            if("".equals(current) || null == current){
                emptyList.add(current);
                continue;
            }
            boolean appeared = false;
            for(Map.Entry<String,List<String>> entry : map.entrySet()){
                String key = entry.getKey();
                List<String> list = entry.getValue();
                if(isAnagrams(key,current)){
                    list.add(current);
                    appeared = true;
                    break;
                }
            }
            if(!appeared){
                List<String> temp = new LinkedList<>();
                temp.add(current);
                map.put(current,temp);
            }
        }
        List<List<String>> ans = new LinkedList<>();
        for(Map.Entry<String,List<String>> entry : map.entrySet()){
            ans.add(entry.getValue());
        }
        if(!emptyList.isEmpty()){
            ans.add(emptyList);
        }
        return ans;
    }
    boolean isAnagrams(String str1,String str2){
        if(str1.length() != str2.length()){
            return false;
        }
        Map<Character,Integer> frequencyMap = new HashMap<>();
        for (int i = 0; i < str1.length(); i++) {
            char c = str1.charAt(i);
            if(frequencyMap.containsKey(c)){
                int value = frequencyMap.get(c) + 1;
                frequencyMap.put(c,value);
            }else{
                frequencyMap.put(c,1);
            }
        }
        for (int i = 0; i < str2.length(); i++) {
            char c = str2.charAt(i);
            if(!frequencyMap.containsKey(c)){
                return false;
            }else{
                int value = frequencyMap.get(c) - 1;
                if(value == 0){
                    frequencyMap.remove(c);
                }else {
                    frequencyMap.put(c,value);
                }
            }
        }
        for(Map.Entry<Character,Integer> entry : frequencyMap.entrySet()){
            if(entry.getValue() != 0){
                return false;
            }
        }
        return true;
    }
}
class GroupAnagramsImpl3 implements GroupAnagrams{

    /**
     * 重写后的解法与官方解法类似，但是会超时，可能是使用了 Set 的原因，自己实现 Hash 表 ， 仍然超时
     * @param strs
     * @return
     */
    @Override
    public List<List<String>> groupAnagrams(String[] strs) {
        int[] hashMap = new int[26];
        List<List<String>> ans = new LinkedList<>();
        List<String> emptyList = new LinkedList<>();
        Map<int[],List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            String current = strs[i];
            if("".equals(current) || null == current){
                emptyList.add(current);
                continue;
            }
            boolean isAppeared = false;
            for(Map.Entry<int[],List<String>> entry : map.entrySet()){
                hashMap = entry.getKey();
                List<String> list = entry.getValue();
                int strsLen = list.get(0).length();
                if(strsLen == current.length()){
                    if(isAnagrams(hashMap,current)){
                        list.add(current);
                        isAppeared = true;
                        break;
                    }
                }
            }
            if(!isAppeared){
                hashMap = new int[26];
                for (int j = 0; j < current.length(); j++) {
                    hashMap[current.charAt(j) - 'a']++;
                }
                List<String> temp = new LinkedList<>();
                temp.add(current);
                map.put(hashMap,temp);
                ans.add(temp);
            }
        }

        if(!emptyList.isEmpty()){
            ans.add(emptyList);
        }
        return ans;
    }
    public boolean isAnagrams(int[] hashMap,String s){
        int[] tempHashMap = hashMap.clone();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(tempHashMap[c - 'a'] == 0){
                return false;
            }else{
                tempHashMap[c - 'a']--;
            }
        }
        return true;
    }
}

/**
 * 抄题解，官方题解的 hash 值是一个String，可能因为这个的原因可以减少时间开销
 */
class GroupAnagramsImpl4 implements GroupAnagrams{

    @Override
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

/**
 *  抄题解，排序后处理
 */
class GroupAnagramsImpl5 implements GroupAnagrams{
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}